Efficient Utilization of Processor’s Capacity in Heterogeneous Distributed System in Tasks Allocation Model

 

Dr. Manisha Sharma1, Dr. Mudit Bansal2

1Astt. Prof., Punjab University, Punjab

2Astt. Prof., S.A.T.I. (Deg.), Vidisha MP

*Corresponding Author E-mail: manishatewaripu@gmail.com; mu_ban@yahoo.com

 

ABSTRACT:

Distributed System (DS) has attracted several researchers by posing several challenging problems. All the processors share single communication cannel. To make the best use of the computational power available it is essential to assign the tasks to that processor whose characteristics are most appropriate for their execution and excessive inter-task communication is avoided. The total processing time of a program is equal to the sum of Execution Times (ET) and Inter Task Communication Times (ITCT). The model discussed in this paper provide an optimal solution for assigning a set of “m” tasks to a set of “n” processors where m >> n, in such a way that allocated load on all the processors are balanced according to the relative speed.

 

KEYWORDS: Distributed System, Allocated Load, Execution Time, Task Allocation, Inter-Task Communication.

 

1. INTRODUCTION:

Distributed system is a computer system in which multiple processors connected together through a high-bandwidth communication link. These links provides a medium for each processor to access data and programs on remote processors. Distribution of resource in DS is seen as a way to improve system throughput and availability. An important resource for DS is user’s program that consists of a set of tasks.

 

Response time is the most important performance measuring factor for real time system. A DS is designed for solving some specific real time application .The system is required to finish a certain task within a specific time limit [17]. The excessive ITCT is always most costly and least reliable factor in the loosely coupled DS. Therefore, an efficient task allocation strategy is required for the proper utilization of computational resources and minimization of ITCT that arises when the interacting tasks reside on different processors. Minimizing ITCT alone may not provide a good assignment. A processor’s load indicates the sum of execution time of the tasks residing on that processor. Balancing the load on processors and minimizing the ITCT can minimize the response time of the system.

 

Many approaches have been reported for solving the task assignment problem in DS and roughly be classified into four categories: Graph theoretical [1,4,6,12,14], Mathematical programming [5,10,13] ,Heuristic approach [2,7,8,15,18],and Probabilistic approaches [3,9,11,16].Many of these methods try to minimize the total processing cost and do not consider load balancing criterion  .

 

In this paper we introduce an algorithm for the static task assignment problem in DS to reduce the job turnaround time and to increase the throughput of the system by proper load balancing on each processor according to the processing speed of the processors and minimizing the ITCT. The algorithm is coded in C++ and several sets of input data are considered to test the efficiency and complexity. It is found that algorithm is suitable for arbitrary number of processors with the random program structure and is workable in all the cases.

The task allocation problem is defined in section-2, the definitions and assumptions have been used while preparing the model are given in section-3, task allocation model is addressed in section-4, implementation of the algorithm is presented in section-5, and finally section-6, gives the conclusion of the model. 

 

REFERENCES:

  1. Richard R.Y., Lee E.Y.S. and Tsuchiya M., “A Task Allocation Model for Distributed Computer System”, IEEE Trans. On Computer, Vol.C-31 pp.41-47, 1982.
  2. Kumar, V. Singh, M. P. and Yadav, P.K., “An Efficient Algorithm for Allocating Tasks to Processors in a Distributed System”, Proc. of the 19th National system conference, SSI, held at Coimbatore, India pp. 82-87, 1995.
  3. Kumar, V. Singh, M.P. and Yadav, P.K., “A Fast Algorithm for Allocating Tasks in Distributed Processing System”, Proc. of the 30th Annual Convention of CSI, held at Hyderabad, India pp. 347-358,1995.
  4. Sagar, G., and Sarje, A.K., “Task Allocation Model for Distributed System”, Int. J. System Science, vol. 22, pp. 1671-1678,1991.
  5. Chou,T.C.K.,& Abraham, J.A.”Load Balancing in Distributed Systems” ,IEEE Trans. Software Engg.,Vol.SE-8,NO.4,PP.401-412,Jul 1982.
  6. Gylys,V.B, & Edwards “Optimal Partitioning of Work load for Distributed Systems” Proc. of the Compcon Fall”76, pp.353-357, 1976.
  7. Elsade A.A.,Wells B.E. “A Heuristic Model for Task Allocation in Heterogeneous Distributed Computing System” The International Journal of Computers and Their Applications. Vol.6, no.1, March 1999.    
  8. Yadav, P.K., Kumar Harendra,.Singh M.P and Kumar Avanish “Heuristic Approach of Tasks Allocation in  Distributing  Processing System” in “International conference on Operation  Research Application in Infrastructure Development “ held  at J.N. Tata Auditorium, IISC  Banglor, India , December 27-29 ,2005.
  9. Singh M.P.,Kumar Harendra ,Yadav P.K.” An Efficient Algorithm for Optimal Tasks Allocation through Optimizing Reliability Index in Heterogeneous Distributed Processing System” in “3rd International Conference on Quality, Reliability and Infocom Technology” held at Indian National Science Academy, New Delhi –India, Dec 2-5.2006.
  10. J.B.Sinclair “Efficient Computation of Optimal Assignment for Distributed Computing, Vol.4, pp.342-362, 1987.
  11. Singh, M.P., Kumar, V. and Kumar, A., “An Efficient Algorithm for Optimizing Reliability Index in Tasks-Allocation”, Acta Ciencia Indica, vol. xxv m, pp. 437-444,1999.
  12. Rotithor, H.G., “Taxonomy of Dynamic Task Scheduling in Distributed Computing Systems”, IEEE Proc. Computer Digit Tech., vol. 14, pp.1-10, 1994.
  13. P.Y.R.Ma. et al “A Task Allocation Model for Distributing Computing System” IEEE Trans. Computers, Vol. 31 no.1.pp. 41-47, Jan. 1982.

14.    Shen C.C and Tsai W.H. “A Graph Matching Approach to Optimal Task Assignment in Distributing Computing System using a Minimax Criterion” IEEE Trans. Computers, Vol. 34,No.3, pp.197-203,Mar.1985.

  1. Kumar Harendra, .Singh M.P and Yadav P.K. “Task Allocation : An Algorithm for   Systematic Allocation of tasks in Distributed computing Environment” in “:National  Seminar on Current trend in Mathematics and computation”  held at  Birla Institute of  Technology,  Ext. Center, NOIDA on December 1, 2005
  2. Srinivasan, Santhanam and Jha. K. Niraj, “Safety and Reliability Driven Task Allocation in Distributed System”, IEEE Transactions on Parallel and Distributed Systems, vol. 10, pp. 238-250, 1999.
  3. Krishna C.M and Shin K.G., “Real-Time System” Mc-Graw- Hill International Edition, 1997.
  4. Casavent, T.L. and Kuhl, J. G., “A Taxonomy of Scheduling in General Purpose Distributed Computing System”, IEEE Transactions on Software Engineering, vol. 14, pp. 141-154, 1988.
  5. John Bresnahan, Rajkumar Kettimuthu, Michael Link and Ian Foster. “Harnessing Multicore Processors for High Speed Secure Transfer”. Proceedings of the 26th IEEE Infocom's High-Speed Networks Workshop, May, 2007
  6. Gaurav Khanna, Umit Catalyurek, Tahsin Kurc, Rajkumar Kettimuthu, P. Sadayappan, Joel Saltz and Ian Foster “Multi-Hop Path Splitting and Multi-Pathing Optimizations for Data Transfers over Shared Wide-Area Networks using GridFTP” Proceedings of the 17th IEEE International Symposium on High-Performance Distributed Computing (HPDC 2008), June 2008
  7. V. Nefedova, R. Jacob, I. Foster, Z. Liu, Y. Liu, E. Deelman, G Mehta, M. Su, K. Vahi.”Automating Climate Science: Large Ensemble Simulations on the TeraGrid with the GriPhyN Virtual Data System”.  Presented at the eScience Conference in Amsterdam, December, 2006

 

 

 

Received on 01.01.2014    Accepted on 25.01.2014

© EnggResearch.net All Right Reserved

Int. J. Tech. 4(1): Jan.-June. 2014; Page 171-180